package bma.common.langutil.core;

import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Fixed length cache with a LRU replacement policy. If cache items implement
 * CacheNotifyObject, they will be informed when they're removed from the cache.
 * 
 * <p>
 * Null keys are not allowed. LruCache is synchronized.
 */
public class LruCache<K, V> {

	// hash table containing the entries. Its size is twice the capacity
	// so it will always remain at least half empty
	private final CacheItem<K, V>[] entries;

	// maximum allowed entries
	private final int capacity;
	private final int mask;

	// number of items in the cache
	private int size;

	// head of the LRU list
	private CacheItem<K, V> head;

	// tail of the LRU list
	private CacheItem<K, V> tail;

	private final LruCacheEvictListener<K, V> listner;

	private final Lock lock;

	/**
	 * Create the LRU cache with a specific capacity.
	 * 
	 * @param initialCapacity
	 *            minimum capacity of the cache
	 */
	@SuppressWarnings("unchecked")
	public LruCache(int initialCapacity, LruCacheEvictListener<K, V> lis,
			Lock lock) {
		int capacity;

		for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) {
		}

		entries = (CacheItem[]) Array.newInstance(CacheItem.class, capacity);
		mask = capacity - 1;

		this.capacity = initialCapacity;
		this.listner = lis;
		this.lock = lock;
	}

	public LruCache(int initialCapacity) {
		this(initialCapacity, null, new ReentrantLock());
	}

	/**
	 * Returns the current number of entries in the cache.
	 */
	public int size() {
		return size;
	}

	protected void lock() {
		if (lock != null)
			lock.lock();
	}

	protected void unlock() {
		if (lock != null)
			lock.unlock();
	}

	/**
	 * Clears the cache
	 */
	public void clear() {

		lock();
		try {
			for (int i = 0; i < entries.length; i++) {
				if (entries[i] != null) {
					addSize(-1);
				}
				entries[i] = null;
			}
			size = 0;
			head = null;
			tail = null;
		} finally {
			unlock();
		}

	}

	/**
	 * Get an item from the cache and make it most recently used.
	 * 
	 * @param key
	 *            key to lookup the item
	 * @return the matching object in the cache
	 */
	public V get(K key) {
		return get(key, false);
	}

	public V touch(K key) {
		return get(key, true);
	}

	protected void touch(CacheItem<K, V> item) {

	}

	protected boolean isEvictable(CacheItem<K, V> item) {
		return false;
	}

	protected CacheItem<K, V> createItem(K key, V value) {
		return new CacheItem<K, V>(key, value);
	}

	protected boolean isOverload() {
		return size >= capacity;
	}

	protected void addSize(int v) {
		this.size += v;
	}

	protected V get(K key, boolean touch) {
		if (key == null)
			return null;

		int hash = key.hashCode() & mask;
		int count = size + 1;
		boolean outdate = false;

		lock();
		try {
			for (; count > 0; count--) {
				CacheItem<K, V> item = entries[hash];

				if (item == null)
					return null;

				if (item.key == key || item.key.equals(key)) {
					if (!touch && isEvictable(item)) {
						outdate = true;
						break;
					}
					if (touch) {
						updateLru(item);
					}
					return item.value;
				}

				hash = (hash + 1) & mask;
			}
		} finally {
			unlock();
		}

		if (outdate)
			remove(key);

		return null;
	}

	/**
	 * Puts a new item in the cache. If the cache is full, remove the LRU item.
	 * 
	 * @param key
	 *            key to store data
	 * @param value
	 *            value to be stored
	 * 
	 * @return old value stored under the key
	 */
	public V put(K key, V value) {
		return localPut(key, value, false);
	}

	public V putIfAbsent(K key, V value) {
		return localPut(key, value, true);
	}

	protected V localPut(K key, V value, boolean putIfAbsent) {
		Preconditions.checkNotNull(key);

		// remove LRU items until we're below capacity
		while (isOverload()) {
			remove(tail.key, false);
		}

		V oldValue = null;

		int hash = key.hashCode() & mask;
		int count = size + 1;

		lock();
		try {
			for (; count > 0; count--) {
				CacheItem<K, V> item = entries[hash];

				// No matching item, so create one
				if (item == null) {
					item = createItem(key, value);
					entries[hash] = item;
					addSize(1);
					item.next = head;
					if (head != null) {
						head.prev = item;
					} else {
						tail = item;
					}
					head = item;
					return null;
				}

				// matching item gets replaced
				if (item.key == key || item.key.equals(key)) {

					if (putIfAbsent) {
						return item.value;
					}

					updateLru(item);

					oldValue = item.value;
					item.value = value;

					break;
				}

				hash = (hash + 1) & mask;
			}
		} finally {
			unlock();
		}

		return oldValue;
	}

	/**
	 * Put item at the head of the lru list. This is always called while
	 * synchronized.
	 */
	private void updateLru(CacheItem<K, V> item) {
		CacheItem<K, V> prev = item.prev;
		CacheItem<K, V> next = item.next;

		if (prev != null) {
			prev.next = next;

			item.prev = null;
			item.next = head;
			head.prev = item;
			head = item;

			if (next != null) {
				next.prev = prev;
			} else {
				tail = prev;
			}
		}
		touch(item);
	}

	/**
	 * Remove the last item in the LRU
	 */
	public boolean removeTail() {
		CacheItem<K, V> last = tail;

		if (last == null) {
			return false;
		} else {
			remove(last.key);
			return true;
		}
	}

	public V remove(K key) {
		return remove(key, true);
	}

	/**
	 * Removes an item from the cache
	 * 
	 * @param key
	 *            the key to remove
	 * 
	 * @return the value removed
	 */
	public V remove(K key, boolean quiet) {
		Preconditions.checkNotNull(key);

		int hash = key.hashCode() & mask;
		int count = size + 1;

		V value = null;
		List<ObjectPair<V, K>> list = null;

		lock();
		try {
			for (; count > 0; count--) {
				CacheItem<K, V> item = entries[hash];

				if (item == null)
					return null;

				if (item.key == key || item.key.equals(key)) {

					if (!quiet && listner != null) {
						if (list == null)
							list = new LinkedList<ObjectPair<V, K>>();
						list.add(new ObjectPair<V, K>(item.value, item.key));
					}

					entries[hash] = null;
					addSize(-1);

					CacheItem<K, V> prev = item.prev;
					CacheItem<K, V> next = item.next;

					if (prev != null) {
						prev.next = next;
					} else {
						head = next;
					}

					if (next != null) {
						next.prev = prev;
					} else {
						tail = prev;
					}

					// Shift colliding entries down
					for (int i = 1; i <= count; i++) {
						int nextHash = (hash + i) & mask;
						CacheItem<K, V> nextItem = entries[nextHash];
						if (nextItem == null)
							break;

						entries[nextHash] = null;
						refillEntry(nextItem);
					}

					value = item.value;
					break;
				}

				hash = (hash + 1) & mask;
			}
		} finally {
			unlock();
		}

		if (list != null) {
			for (ObjectPair<V, K> op : list) {
				this.listner.onEviction(op.getAttribute(), op.getValue());
			}
		}

		if (count < 0)
			throw new RuntimeException("internal cache error");

		return value;
	}

	/**
	 * Put the item in the best location available in the hash table.
	 */
	private void refillEntry(CacheItem<K, V> item) {
		int baseHash = item.key.hashCode();

		for (int count = 0; count < size + 1; count++) {
			int hash = (baseHash + count) & mask;

			if (entries[hash] == null) {
				entries[hash] = item;
				return;
			}
		}
	}

	/**
	 * Returns the keys stored in the cache
	 */
	public Iterator<K> keys() {
		KeyIterator iter = new KeyIterator();
		iter.init(this);
		return iter;
	}

	/**
	 * Returns keys stored in the cache using an old iterator
	 */
	protected Iterator<K> keys(KeyIterator oldIter) {
		KeyIterator iter = oldIter;
		iter.init(this);
		return iter;
	}

	/**
	 * Returns the values in the cache
	 */
	public Iterator<V> values() {
		ValueIterator iter = new ValueIterator();
		iter.init(this);
		return iter;
	}

	protected Iterator<V> values(ValueIterator oldIter) {
		ValueIterator iter = oldIter;
		iter.init(this);
		return iter;
	}

	public int getCapacity() {
		return capacity;
	}

	public void removeValue(Object value) {
		for (int i = 0; i < entries.length; i++) {
			CacheItem<K, V> item = entries[i];
			if (item != null) {
				if (item.value == value) {
					remove(item.key);
					return;
				}
			}
		}
	}

	/**
	 * A cache item
	 */
	protected static class CacheItem<IK, IV> {
		CacheItem<IK, IV> prev;

		CacheItem<IK, IV> next;

		protected IK key;

		protected IV value;

		public IK getKey() {
			return key;
		}

		public IV getValue() {
			return value;
		}

		public CacheItem(IK key, IV value) {
			this.key = key;
			this.value = value;
		}
	}

	/**
	 * Iterator of cache keys
	 */
	protected class KeyIterator implements Iterator<K> {
		CacheItem<K, V> item;

		void init(LruCache<K, V> cache) {
			item = cache.head;
		}

		@Override
		public boolean hasNext() {
			return item != null;
		}

		@Override
		public K next() {
			K value = item.key;
			item = item.next;
			return value;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	/**
	 * Iterator of cache values
	 */
	protected class ValueIterator implements Iterator<V> {

		CacheItem<K, V> item;

		void init(LruCache<K, V> cache) {
			item = cache.head;
		}

		@Override
		public boolean hasNext() {
			return item != null;
		}

		@Override
		public V next() {
			V value = item.value;
			item = item.next;
			return value;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	public String snapshot() {
		StringBuilder sb = new StringBuilder(128);
		Iterator<K> it = keys();
		while (it.hasNext()) {
			K k = it.next();
			sb.append(k).append("=").append(get(k));
			if (it.hasNext())
				sb.append(",");
		}
		return sb.toString();
	}

	public static class Expire<K2, V2> extends LruCache<K2, V2> {

		protected static class ExpireCacheItem<IK, IV> extends
				CacheItem<IK, IV> {

			protected long time;

			public ExpireCacheItem(IK key, IV value) {
				super(key, value);
				this.time = System.currentTimeMillis();
			}

		}

		protected final int timeToIdle;

		public Expire(int initialCapacity, int timeToIdle,
				LruCacheEvictListener<K2, V2> lis, Lock lock) {
			super(initialCapacity, lis, lock);
			this.timeToIdle = timeToIdle;
		}

		public Expire(int initialCapacity, int timeToIdle) {
			super(initialCapacity);
			this.timeToIdle = timeToIdle;
		}

		@Override
		protected void touch(CacheItem<K2, V2> item) {
			((ExpireCacheItem<K2, V2>) item).time = System.currentTimeMillis();
		}

		@Override
		protected boolean isEvictable(CacheItem<K2, V2> item) {
			if (((ExpireCacheItem<K2, V2>) item).time + timeToIdle < System
					.currentTimeMillis()) {
				return true;
			}
			return false;
		}

		@Override
		protected CacheItem<K2, V2> createItem(K2 key, V2 value) {
			return new ExpireCacheItem<K2, V2>(key, value);
		}

	}
}
